"""
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。
"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root):
        # depth = 0
        # max_depth = 0
        # def dfs(root):
        #     nonlocal depth, max_depth
        #     if not root: return
        #     depth += 1
        #     dfs(root.left)
        #     dfs(root.right)
        #     if depth > max_depth:
        #         max_depth = depth
        #     depth -= 1
        # dfs(root)
        # return max_depth
        def bfs(level):
            nonlocal depth
            if not level: return
            depth += 1
            for i in range(len(level)):
                node = level.pop()
                if not node: continue
                if node.left: level.insert(0, node.left)
                if node.right: level.insert(0, node.right)
            bfs(level)
        depth = 0
        if not root: return depth
        bfs([root])
        return depth

